package com.sheng.leetcode.year2022.month11.day14;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/11/14
 *<p>
 * 805. 数组的均值分割
 *<p>
 * 给定你一个整数数组 nums<p>
 * 我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，<p>
 * 使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。<p>
 * 如果可以完成则返回true ， 否则返回 false  。<p>
 * 注意：对于数组 arr ,  average(arr) 是 arr 的所有元素除以 arr 长度的和。<p>
 *<p>
 * 示例 1:<p>
 * 输入: nums = [1,2,3,4,5,6,7,8]<p>
 * 输出: true<p>
 * 解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。<p>
 *<p>
 * 示例 2:<p>
 * 输入: nums = [3,1]<p>
 * 输出: false<p>
 *<p>
 * 提示:<p>
 * 1 <= nums.length <= 30<p>
 * 0 <= nums[i] <= 10^4<p>
 */
public class LeetCode0805 {

    @Test
    public void test01() {
        int[] nums = {1,2,3,4,5,6,7,8};
//        int[] nums = {3, 1};
        System.out.println(new Solution().splitArraySameAverage(nums));
    }
}
class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        /**
         * 题目要求，即取数组中的一部分元素，这部分元素的平均值等于原数组的平均值
         * 即找出来的部分元素的和为 sum * (元素个数) / length
         */
        if (nums.length == 1) {
            return false;
        }
        if (nums.length == 2) {
            return nums[0] == nums[1];
        }
        Arrays.sort(nums);
        int length = nums.length;
        int sum = Arrays.stream(nums).sum();

        for (int i = 1; i <= length / 2; i++) {
            // 满足当前条件，代表存在 51 * 5 % 5 == 0 这种情况
            if (sum * i % length == 0) {
                // 是否存在长度为 i 的元素之和为 sum * i / length
                if (dfs(nums, i, sum * i / length, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * @param ints 数组
     * @param n 数组长度
     * @param sum 该长度的数组的总和要等于的数
     * @param index 起始坐标
     * @return boolean
     */
    private boolean dfs(int[] ints, int n, int sum, int index) {
        // 长度和总和同时等于 0 时，代表找到了对应元素
        if (sum == 0 && n == 0) {
            return true;
        }
        // 长度不等于 0 时进行下一次循环
        if (n != 0) {
            for (int i = index; i < ints.length; i++) {
                // 数组中当前元素等于前一个元素时，结束当前循环
                if (i > index && ints[i] == ints[i - 1]) {
                    continue;
                }
                // dfs，对总和进行相减
                if (dfs(ints, n - 1, sum - ints[i], i + 1)) {
                    return true;
                }
            }
        }
        return false;
    }
}
